/*
 * @lc app=leetcode.cn id=17 lang=golang
 *
 * [17] 电话号码的字母组合
 */

// @lc code=start

func letterCombinations(digits string) []string {
	var digits_map = map[byte]string{
		'2': "abc",
		'3': "def",
		'4': "ghi",
		'5': "jkl",
		'6': "mno",
		'7': "pqrs",
		'8': "tuv",
		'9': "wxyz",
	}
	ans := []string{}
	n := len(digits)
	if n == 0 {
		return ans
	}
	temp := []byte{}

	var dfs func(index int)
	dfs = func(index int) {
		if index == n {
			ans = append(ans, string(append([]byte{}, temp...)))
			return
		}
		for _, v := range digits_map[digits[index]] {
			temp = append(temp, byte(v))

			dfs(index + 1)

			temp = temp[:len(temp)-1]
		}
	}
	dfs(0)
	return ans
}

// @lc code=end

